#include <math.h>
#include <iostream>
#include <queue>
#include <vector>

using std::cout;
using std::endl;
using std::vector;
using std::ostream;
using std::priority_queue;

void test0()
{
    vector<int> arr{6, 1, 3, 2, 7, 8, 5, 4, 9};
    //Q:默认情况下，优先级队列的比较方式也是小于符号
    //但优先级队列中的元素是按降序排列的
    //相比set/map而言，默认情况下也是小于符号比较，但是升序排列的
    //为什么会这样?
    //
    //A: 这与优先级队列的底层实现有关， 底层是采用的堆排序
    //默认情况下，得到的是一个大顶堆.其比较的策略是：
    //每次都是用堆顶的元素与新添加进来的元素进行比较
    //std::less<int> lt;
    //lt(heapTopElement, newElement) ,
    //当该判断返回true时，意味着新的元素大于堆顶的元素，那么
    //heapTopElement进行堆的调整, 新元素newElement
    //就占据堆顶的位置了
    priority_queue<int> que;
    for(int i = 0; i < arr.size(); ++i) {
        que.push(arr[i]);
        cout << "当前队列中优先级最高的是: " << que.top() << endl;
    }
    cout << endl;

    cout << "元素出队:" << endl;
    while(!que.empty()) {
        //top中就是优先级最高的元素
        cout << que.top() << endl;
        //将优先级最高的元素出队
        que.pop();
    }
}

class Point
{
public:
    Point(int ix = 0, int iy =0)
    : _ix(ix)
    , _iy(iy)
    {
        cout << "Point(int=0,int=0)" << endl;
    }

#if 0
    Point(const Point & rhs)
    : _ix(rhs._ix)
    , _iy(rhs._iy)
    {
        cout << "Point(const Point & rhs)" << endl;
    }

    Point & operator=(const Point & rhs)
    {
        cout << "operator=(const Point &)" << endl;
        if(this != &rhs) {
            _ix = rhs._ix;
            _iy = rhs._iy;
        }
        return *this;
    }

    Point(Point && rhs)
    : _ix(std::move(rhs._ix))
    , _iy(std::move(rhs._iy))
    {
        cout << "Point(Point&&)" << endl;
    }
#endif
    
    friend ostream & operator<<(ostream & os, const Point & rhs);

    int getX() const {  return _ix; }
    int getY() const {  return _iy; }

    double getDistance() const
    {
        return sqrt(_ix * _ix + _iy * _iy);
    }

private:
    int _ix;
    int _iy;
};

bool operator<(const Point & lhs, const Point & rhs)
{
    return lhs.getDistance() < rhs.getDistance();
}

ostream & operator<<(ostream & os, const Point & rhs)
{
    os << "(" << rhs._ix
       << "," << rhs._iy
       << ")";
    return os;
}

void test1()
{
    //这里默认兼容了第二个和第三个模板参数
    //std::vector<Point>
    //std::less<Point>
    priority_queue<Point> que;
    que.emplace(1, 1);
    que.emplace(2, 2);
    que.emplace(3, 3);
    que.emplace(2, 2);
    que.emplace(4, 4);
    while(!que.empty()) {
        cout << que.top() << endl;
        que.pop();
    }
}

struct MyComparator
{
    bool operator()(const Point & lhs, const Point & rhs) const
    {
        return lhs.getDistance() < rhs.getDistance();
    }
};

void test2()
{
    cout << "\ntest2()" << endl;
    //自定义第二个和第三个模板参数
    priority_queue<Point, std::deque<Point>, MyComparator> que;
    que.emplace(1, 1);
    que.emplace(2, 2);
    que.emplace(3, 3);
    que.emplace(2, 2);
    que.emplace(4, 4);
    while(!que.empty()) {
        cout << que.top() << endl;
        que.pop();
    }
}
int main()
{
    /* test0(); */
    /* test1(); */
    test2();
    return 0;
}

